package NiuKe.ComSort;


import java.util.Arrays;
import java.util.Stack;

class comSort {
    /**
     * 直接插入排序-推荐使用
     * 时间复杂度O（N^2)
     *      最好的情况是O（N）：对于直接插入排序来说，最好的情况就是数据有序的时候
     *      可以推导出结论：当数据越有序，时间效率越高
     * 空间复杂度O（1）
     * 稳定性：稳定的
     * 一个稳定的排序，可以实现为不稳定的排序，但是一个本身不稳定的排序，是不可以
     * 变成稳定的排序的。
     * @param array
     */
    public  void insertSort(int[] array){
//        思想：假定第一个元素有序，从第二个元素开始回退排序
        for (int i = 1; i < array.length; i++) {
            int tmp=array[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if (array[j]>array[j+1])array[j+1]=array[j];
//                当array[j]<tmp的时候，说明有序了
                else break;
//                为什么不在else中写 array[j+1]=tmp;因为当j为-1的时候进不来
            }
            //j回退到了小于0的地方
            array[j+1]=tmp;
        }
    }

        /**
         * 希尔排序，
         * 时间复杂度和增量有关系【n^1.3-n^1.5】
         * 空间复杂度O（1）
         * 稳定性：不稳定
         * @param array
         * @param gap
         */

        //待排序的序列
        private   void shell(int [] array,int gap){
            for (int i =gap; i < array.length; i++) {
                int tmp=array[i];
                int j = i-gap;
                for (;j >0 ; j-=gap) {
                    if (array[j]>tmp)array[j+gap]=array[j];
                    else break;
                }
                array[j+gap]=tmp;
            }
        }
        public  void shellSort(int[] array){
            int gap=array.length;
            while (gap>1){
                shell(array,gap);
                gap/=2;
            }
            shell(array,1);
        }

    /**
     * 选择排序-不推荐使用-很垃圾的
     * 时间复杂度O（N^2)
     * 稳定性：不稳定
     * @param array
     */
    public void choiceSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = i+1; j < array.length; j++) {
                if (array[j]<array[i]){
                    int tmp=array[i];
                    array[i]=array[j];
                    array[j]=tmp;
                }
            }
        }
    }

    /**堆排序
     * 时间复杂度O（NlogN)
     * @param array
     */
    public void heatSort(int[] array){
        createHeap(array);
        int end=array.length-1;
        while (end>0){
            int tmp=array[0];
            array[0]=array[end];
            array[end]=tmp;
            shiftDown(array,0,end);
            end--;
        }
    }

    private static void createHeap(int[] array){
        for (int parent = (array.length-1-1)/2; parent >=0 ; parent--) {
            shiftDown(array,parent,array.length);
        }
    }
    private static void shiftDown(int[] array,int parent,int len){
        int child=2*parent+1;
        while (child<len){
            if (child+1<len&&array[child]<array[child+1]){
                child++;//child下标就是左右孩子最大值的下标
            }
            if (array[child]>array[parent]){
                int tmp=array[child];
                array[child]=array[parent];
                array[parent]=tmp;
                parent=child;
                child=2*parent+1;
            }else break;
        }
    }

    /**冒泡排序
     * 时间复杂度O（N^2)
     * 空间复杂度）O（1）
     * 稳定性：稳定
     * @param array
     */
    public void bubbleSort(int[] array){
        for (int i = 0; i <array.length ; i++) {
            //i是趟数
            boolean flg=false;
            for (int j = 0; j <array.length-1; j++) {
                if (array[j]>array[j+1]){
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                    flg=true;
                }
            }
            if (flg==false)break;
        }
    }


    /**快速排序
     * 时间复杂度（最好）【每次可以均匀分割待排序序列】：O(Nlogn)
     * 最坏【数据有序，或者逆序的情况O（N^2);
     * 空间复杂度：(logn)
     * 最坏【单分支的一棵树】O（N）
     *    稳定性：不稳定
     * @param array
     */
    public void FquickSort(int[] array){
        //非递归实现
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int pivot=partition(array,left,right);
        if (pivot >left+1){
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot<right-1){
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left= stack.pop();
            pivot=partition(array,left,right);
            if (pivot>left+1){
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot<right-1){
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    public void quickSort(int[] array){
        quick(array,0,array.length-1);
    }
    private void quick(int[] array,int left,int right){
        if (left>=right)return;
//        找基准之前，找到中间大小的值
        int midValIndex=findMidValIndex(array,left,right);
        int tmp=array[left];
        array[left]=array[midValIndex];
        array[midValIndex]=tmp;

        int pivot=   partition(array,left,right);//基准

        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    private int findMidValIndex(int[] array,int left,int right){
        int mid=left+((right-left)>>>1);
        if (array[left]<array[right]){
            if (array[mid]<array[left])return left;
            else if (array[mid]>array[right])return right;
            else return mid;
        }else {
            if (array[mid]>array[left])return left;
            else if (array[mid]<array[right])return right;
            else return mid;
        }

    }
    private int partition(int[] array,int start,int end){
        int tmp=array[start];
        while (start<end){
            while (start<end && array[end]>=tmp){//=号必须有，防止死循环
                end--;
            }
            //end下标遇到了小于tmp的值，然后将值放到start值
            array[start]=array[end];
            while (array[start]<=tmp&&start<end){
                start++;
            }
            //start下标遇到>tmp的值,将值放到end
            array[end]=array[start];
        }
        array[start]=tmp;
        return start;
    }

    /**归并排序
     * 时间复杂度O（N*logN）
     * 空间复杂度O（N）
     * 稳定性：稳定
     * 如果：array[s1]<=array[s2]不取等号那么就是不稳定的
     * 学过的排序只有3个是稳定的：
     * 冒泡 插入 归并
     * @param array
     */
    public void FmergeSort(int[] array){
//        归并排序的非递归方式
        int gap=1;//每组的数据个数
        while (gap<array.length){
            //每次遍历需要确定归并的区间
            for (int i = 0; i < array.length; i+=gap*2) {
                int left=i;
                int mid=left+gap-1;
                if(mid>=array.length-1){
                    //防治越界
                    mid=array.length-1;
                }
                int right=mid+gap;
                if (right>=array.length){
                    //防治越界
                    right=array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap*=2;
        }
    }
    public void mergeSort(int[] array){
        mergeSortInternal(array,0,array.length-1);
    }
    private void mergeSortInternal(int[] array,int low,int high){
        //看这个操作有没有像二叉树的后序遍历
        //不断进行二分的操作
        if (low>=high)return;//分无可分就停止

        int mid=low+((high-low)>>>1);//mid 取中间值

        mergeSortInternal(array,low,mid);//二分左边

        mergeSortInternal(array,mid+1,high);//二分右边

        merge(array,low,mid,high);//合并
    }
    private void merge(int[] array,int low,int mid,int high){
        //合并俩个有序数组么
        int[] tmp=new int[high-low+1];
        int k=0;

        int s1=low;
        int e1=mid;
        int s2=mid+1;
        int e2=high;

        while (s1<=e1 && s2<=e2) {
            if (array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            } else {
                tmp[k++] = array[s2++];
            }
        }
        while (s1<=e1){
            tmp[k++]=array[s1++];
        }
        while (s2<=e2){
            tmp[k++]=array[s2++];
        }
        //拷贝tmp数组的元素，放入原来的数组array当中
        for (int i = 0; i < k; i++) {
            array[i+low]=tmp[i];
        }

    }

    /**
     * 计数排序
     * 时间复杂度O（N）
     * 空间复杂度O（M）M:代表当前的数据的范围
     * 稳定性：当前不稳定，但是能改的稳定
     * @param array
     */

    public void countingSort(int[] array){
        int maxVal=array[0];
        int minVal=array[0];
        for (int i = 1; i <array.length ; i++) {
            if (array[i]<minVal){
                minVal=array[i];
            }
            if (array[i]>maxVal){
                maxVal=array[i];
            }
        }
        //已经找到最大值和最小值
        int[] count=new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            int index=array[i];
            //不是i存放因为你的数组长度是最大值减最小值创建的
            count[index-minVal]++;
        }
        //将计数数组中array数组每个数字出现的次数统计好了
        int indexArray=0;
        for (int i = 0; i < count.length; i++) {

            while (count[i]>0){
//                因为不一定是i出现俩次
                array[indexArray]=i+minVal;
                count[i]--;//拷贝依次后数据就少一个
                indexArray++;//原数组往后走
            }
        }
    }


}
public class Test {
    public static void main(String[] args) {
        comSort sort=new comSort();
        int[] array={1,5,3,4,2};
       sort.FmergeSort(array);
        System.out.println(Arrays.toString(array));
    }
}
